"""
计数排序适用于整数排序，通过统计每个元素的出现次数，再根据次数重建有序数组，时间复杂度为 O (n + k)（k 为数据范围）。

仅适用于整数（或可映射为整数的离散值）
时间复杂度稳定为 O (n + k)（k 为数据范围）
空间复杂度较高（取决于数据范围 k）

"""


def counting_sort(arr):
    """
    计数排序实现（适用于非负整数）

    参数:
        arr: 待排序的非负整数列表
    返回:
        排序后的列表
    """
    if not arr:  # 处理空列表
        return arr

    # 1. 确定数据范围（找到最大值和最小值）
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1  # 数据范围大小

    # 2. 创建计数数组，统计每个元素的出现次数
    count = [0] * range_val  # 初始化计数数组（长度为数据范围）
    for num in arr:
        # 计算元素在计数数组中的索引（偏移量处理负数）
        count[num - min_val] += 1

    # 3. 计算计数数组的前缀和（确定每个元素的最终位置）
    for i in range(1, len(count)):
        count[i] += count[i - 1]  # 前缀和：count[i]表示<=i+min_val的元素个数

    # 4. 反向遍历原数组，构建结果（保证稳定性）
    result = [0] * len(arr)  # 初始化结果数组
    for num in reversed(arr):  # 反向遍历避免覆盖未处理的元素
        # 计算当前元素在结果数组中的位置
        index = count[num - min_val] - 1
        result[index] = num
        count[num - min_val] -= 1  # 减少计数，确保下一个相同元素位置正确

    return result


# 测试计数排序
if __name__ == "__main__":
    test_arr = [4, 2, 2, 8, 3, 3, 1]
    print("计数排序前:", test_arr)
    print("计数排序后:", counting_sort(test_arr))